package com.jake.data_structure_learning;

import org.springframework.stereotype.Service;

@Service
public class StringService {

    /**
     * 查找 一个函数来查找字符串数组中的最长公共前缀。
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null) {
            return null;
        }
        int minLength = 0;
        for (int i = 0; i < strs.length; i++) {
            if (i == 0) {
                minLength = strs[i].length();
            }
            if (strs[i].length() < minLength) {
                minLength = strs[i].length();
            }
        }

        StringBuilder sb = new StringBuilder("");
        for (int j = 0; j < minLength; j++) {
            char first = 0;
            for (int i = 0; i < strs.length; i++) {

                if (i == 0) {
                    first = strs[i].charAt(j);
                }
                if (first == strs[i].charAt(j)) {

                } else {
                    return sb.toString();
                }
                if (i == strs.length - 1) {
                    sb.append(strs[i].charAt(j));
                }
            }
        }
        return sb.toString();
    }


    /**
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s == null || "".equals(s)) {
            return "";
        }
        StringBuilder sb = new StringBuilder("");
        int first = 0;
        int end = 0;
        int length = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    int temp = j - i + 1;
                    if (temp > length) {
                        first = i;
                        end = j;
                        length = temp;
                    }
                }
            }
        }
        for (int i = first; i <= end; i++) {
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }


    /**
     * 给定一个字符串，逐个翻转字符串中的每个单词。
     *
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        if (s == null || "".equals(s)) {
            return "";
        }
        StringBuilder sb = new StringBuilder("");
        String[] strs = s.split(" ");
        int index = 0;
        for (int i = strs.length - 1; i >= 0; i--) {
            if ("".equals(strs[i])) {
                continue;
            }
            if (index == 0) {
                sb.append(strs[i]);
            } else {
                sb.append(" " + strs[i]);
            }
            index++;
        }
        return sb.toString();
    }

    /**
     * 实现 strStr() 函数。
     * <p>
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     * <p>
     * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        if (needle == null || "".equals(needle)) {
            return 0;
        }
        if (haystack == null || "".equals(haystack)) {
            return -1;
        }
        if (needle.length() > haystack.length()) {
            return -1;
        }
        if (haystack.equals(needle)) {
            return 0;
        }
        int index = -1;
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            boolean flag = true;
            for (int j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                }
            }
            if (flag) {
                index = i;
                break;
            }
        }
        return index;
    }

    /**
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
     * <p>
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * <p>
     * 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
     * 示例 1：
     * <p>
     * 输入：["h","e","l","l","o"]
     * 输出：["o","l","l","e","h"]
     * 示例 2：
     * <p>
     * 输入：["H","a","n","n","a","h"]
     * 输出：["h","a","n","n","a","H"]
     *
     * @param s
     */
    public void reverseString(char[] s) {
        if (s == null || s.length == 0) {
            return;
        }

        int i = 0;
        int j = s.length - 1;
        while (i < j) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
}
